
后端的任务是从模块的LLVM IR中创建优化的机器码。IR是后端接口，可以使用C++接口或以文本形式创建，IR也是从AST生成的。

\mySubsubsection{2.6.1.}{LLVM IR的文本表示}

\begin{enumerate}
\item
向用户询问每个变量的值。

\item
计算表达式的值。

\item
输出结果。
\end{enumerate}

为了让用户提供一个变量的值并打印结果，使用了两个库函数:calc\_read()和calc\_write()。对于with a: 3*a表达式，生成的IR如下所示:

\begin{enumerate}
\item
必须声明库函数，就像在C中一样，语法也类似于C。函数名之前的类型是返回类型。用括号括起来的类型名是参数类型。声明可以出现在文件的任何地方:

\begin{shell}
declare i32 @calc_read(ptr)
declare void @calc_write(i32)
\end{shell}

\item
calc\_read()函数将变量名作为参数。下面的构造定义了一个常量保存a，以及使用空字节作为C字符串的结束符:

\begin{shell}
@a.str = private constant [2 x i8] c"a\00"
\end{shell}

\item
其遵循main()函数。省略参数名，因为没有使用。和C语言一样，函数体用大括号括起来:

\begin{shell}
define i32 @main(i32, ptr) {
\end{shell}

\item
每个基本块必须有一个标签，这是函数的第一个基本块，将其命名为entry:

\begin{shell}
entry:
\end{shell}

\item
calc\_read()用来读取a变量的值。嵌套的getelemenptr指令执行索引计算，以计算指向字符串常量第一个元素的指针。函数结果赋值给未命名的\%2变量。

\begin{shell}
    %2 = call i32 @calc_read(ptr @a.str)
\end{shell}

\item
接下来，将变量乘以3:

\begin{shell}
    %3 = mul nsw i32 3, %2
\end{shell}

\item
结果通过调用calc\_write()函数输出在控制台上:

\begin{shell}
    call void @calc_write(i32 %3)
\end{shell}

\item
最后，main()函数返回0，表示执行成功:

\begin{shell}
    ret i32 0
}
\end{shell}

\end{enumerate}

LLVM IR中的每个值都是有类型的，i32表示32位整数类型，ptr表示指针。

\begin{myNotic}{Note}
以前版本的LLVM使用类型化指针。例如：在LLVM中，指向字节的指针表示为i8*。从LLVM 16开始，不透明指针是默认的。不透明指针只是一个指向内存的指针，不携带关于类型的信息。LLVM IR中的符号是ptr。
\end{myNotic}

既然现在已经清楚了IR的样子，让我们使用AST生成它吧。

\mySubsubsection{2.6.2.}{使用AST生成IR}

CodeGen.h头文件中提供的接口非常少:

\begin{cpp}
#ifndef CODEGEN_H
#define CODEGEN_H

#include "AST.h"

class CodeGen
{
    public:
    void compile(AST *Tree);
};
#endif
\end{cpp}

AST包含了这些信息，所以使用一个访问器来遍历AST。CodeGen.cpp文件的实现如下所示:

\begin{enumerate}
\item
所需的包含在文件的顶部:

\begin{cpp}
#include "CodeGen.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/Support/raw_ostream.h"
\end{cpp}

\item
LLVM库的命名空间用于名称查找:

\begin{cpp}
using namespace llvm;
\end{cpp}

\item
首先，在访问者中声明一些私有成员。在LLVM中，每个编译单元都由Module类表示，访问者有一个指向模块M的指针。为了便于生成IR，使用了Builder (IRBuilder<>类型)。LLVM有一个类层次结构来表示IR中的类型，可以从LLVM上下文中查找i32等基本类型的实例。

这些基本类型经常使用。为了避免重复查找，这里缓存了所需的类型实例:VoidTy、Int32Ty、PtrTy和Int32Zero。成员V是当前计算的值，通过树遍历更新。最后，nameMap将变量名映射到calc\_read()函数返回的值:

\begin{cpp}
namespace {
class ToIRVisitor : public ASTVisitor {
    Module *M;
    IRBuilder<> Builder;
    Type *VoidTy;
    Type *Int32Ty;
    PointerType *PtrTy;
    Constant *Int32Zero;
    Value *V;
    StringMap<Value *> nameMap;
\end{cpp}

\item
构造函数初始化所有成员:

\begin{cpp}
public:
    ToIRVisitor(Module *M) : M(M), Builder(M->getContext())
    {
        VoidTy = Type::getVoidTy(M->getContext());
        Int32Ty = Type::getInt32Ty(M->getContext());
        PtrTy = PointerType::getUnqual(M->getContext());
        Int32Zero = ConstantInt::get(Int32Ty, 0, true);
    }
\end{cpp}

\item
对于每个函数，必须创建一个FunctionType实例。在C++术语中，这是一个函数原型。函数本身是用函数实例定义的。run()方法首先在LLVM IR中定义main()函数:

\begin{cpp}
    void run(AST *Tree) {
        FunctionType *MainFty = FunctionType::get(
            Int32Ty, {Int32Ty, PtrTy}, false);
        Function *MainFn = Function::Create(
            MainFty, GlobalValue::ExternalLinkage,
            "main", M);
\end{cpp}

\item
然后用entry标签创建BB基本块，并将其添加到IR构建器:

\begin{cpp}
        BasicBlock *BB = BasicBlock::Create(M->getContext(),
                                            "entry", MainFn);
        Builder.SetInsertPoint(BB);
\end{cpp}

\item
准备工作完成后，就可以开始遍历树了:

\begin{cpp}
            Tree->accept(*this);
\end{cpp}

\item
遍历树之后，通过调用calc\_write()函数输出计算值，必须创建函数原型(FunctionType的实例)。唯一的参数是当前值V:

\begin{cpp}
            FunctionType *CalcWriteFnTy =
                FunctionType::get(VoidTy, {Int32Ty}, false);
            Function *CalcWriteFn = Function::Create(
                CalcWriteFnTy, GlobalValue::ExternalLinkage,
                "calc_write", M);
            Builder.CreateCall(CalcWriteFnTy, CalcWriteFn, {V});
\end{cpp}

\item
生成main()函数，并返回0结束:

\begin{cpp}
            Builder.CreateRet(Int32Zero);
        }
\end{cpp}

\item
WithDecl节点保存声明的变量的名称，为calc\_read()函数创建一个函数原型:

\begin{cpp}
    virtual void visit(WithDecl &Node) override {
        FunctionType *ReadFty =
            FunctionType::get(Int32Ty, {PtrTy}, false);
        Function *ReadFn = Function::Create(
            ReadFty, GlobalValue::ExternalLinkage,
            "calc_read", M);
\end{cpp}

\item
该方法循环遍历变量名:

\begin{cpp}
        for (auto I = Node.begin(), E = Node.end(); I != E;
            ++I) {
\end{cpp}

\item
对于每个变量，创建一个带有变量名的字符串:

\begin{cpp}
        StringRef Var = *I;
        Constant *StrText = ConstantDataArray::getString(
            M->getContext(), Var);
        GlobalVariable *Str = new GlobalVariable(
            *M, StrText->getType(),
            /*isConstant=*/true,
            GlobalValue::PrivateLinkage,
            StrText, Twine(Var).concat(".str"));
\end{cpp}

\item
创建调用calc\_read()函数的IR代码，使用上一步中创建的字符串作为参数传递:

\begin{cpp}
        CallInst *Call =
            Builder.CreateCall(ReadFty, ReadFn, {Str});
\end{cpp}

\item
返回值存储在mapNames映射中供以后使用:

\begin{cpp}
        nameMap[Var] = Call;
    }
\end{cpp}

\item
树的遍历将继续使用下面的表达式:

\begin{cpp}
    Node.getExpr()->accept(*this);
};
\end{cpp}

\item
Factor节点可以是变量名，也可以是数字。对于变量名，将在mapNames映射中查找该值。对于数字，将值转换为整数并转换为常数值:

\begin{cpp}
virtual void visit(Factor &Node) override {
    if (Node.getKind() == Factor::Ident) {
        V = nameMap[Node.getVal()];
    } else {
        int intval;
        Node.getVal().getAsInteger(10, intval);
        V = ConstantInt::get(Int32Ty, intval, true);
    }
};
\end{cpp}

\item
对于BinaryOp节点，必须使用正确的计算操作:

\begin{cpp}
virtual void visit(BinaryOp &Node) override {
    Node.getLeft()->accept(*this);
    Value *Left = V;
    Node.getRight()->accept(*this);
    Value *Right = V;
    switch (Node.getOperator()) {
        case BinaryOp::Plus:
        V = Builder.CreateNSWAdd(Left, Right); break;
        case BinaryOp::Minus:
        V = Builder.CreateNSWSub(Left, Right); break;
        case BinaryOp::Mul:
        V = Builder.CreateNSWMul(Left, Right); break;
        case BinaryOp::Div:
        V = Builder.CreateSDiv(Left, Right); break;
    }
};
};
}
\end{cpp}

\item
至此，访问者类就完成了。compile()方法创建全局上下文和模块，运行树遍历，并将生成的IR转储到控制台:

\begin{cpp}
void CodeGen::compile(AST *Tree) {
    LLVMContext Ctx;
    Module *M = new Module("calc.expr", Ctx);
    ToIRVisitor ToIR(M);
    ToIR.run(Tree);
    M->print(outs(), nullptr);
}
\end{cpp}

\end{enumerate}

现在，已经实现了编译器的前端，从读取源代码到生成IR。所有这些组件必须在用户输入时一起工作，这是编译器驱动程序的任务，还需要实现运行时所需的函数。这两个都是下一节的主题。

\mySubsubsection{2.6.3.}{缺失的部分——驱动程序和运行时库}

前几节中的所有阶段都由Calc.cpp驱动程序粘合在一起:声明输入表达式的参数，初始化LLVM，并调用前几节中的所有代码:

\begin{enumerate}
\item
首先，包含所需的头文件:

\begin{cpp}
#include "CodeGen.h"
#include "Parser.h"
#include "Sema.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/InitLLVM.h"
#include "llvm/Support/raw_ostream.h"
\end{cpp}

\item
LLVM自带声明命令行选项的系统，只需要为需要的每个选项声明一个静态变量。在此过程中，该选项会注册到一个全局命令行解析器中。这种方法的优点是，每个组件都可以在需要时添加命令行选项。我们为输入表达式声明一个选项:

\begin{cpp}
static llvm::cl::opt<std::string>
    Input(llvm::cl::Positional,
        llvm::cl::desc("<input expression>"),
        llvm::cl::init(""));
\end{cpp}

\item
main()函数中，首先初始化LLVM库。需要ParseCommandLineOptions()来处理命令行上给出的选项。这还处理帮助信息的输出，若发生错误，使用此方法将结束应用程序的运行:

\begin{cpp}
int main(int argc, const char **argv) {
    llvm::InitLLVM X(argc, argv);
    llvm::cl::ParseCommandLineOptions(
        argc, argv, "calc - the expression compiler\n");
\end{cpp}

\item
接下来，调用词法分析器和解析器。在语法分析之后，检查是否发生了任何错误。若是这种情况，则退出编译器，并返回一个表示失败的错误码:

\begin{cpp}
    Lexer Lex(Input);
    Parser Parser(Lex);
    AST *Tree = Parser.parse();
    if (!Tree || Parser.hasError()) {
        llvm::errs() << "Syntax errors occured\n";
        return 1;
    }
\end{cpp}

\item
若有语义错误，也会这样做:

\begin{cpp}
    Sema Semantic;
    if (Semantic.semantic(Tree)) {
        llvm::errs() << "Semantic errors occured\n";
        return 1;
    }
\end{cpp}

\item
作为驱动程序的最后一步，将调用代码生成器:

\begin{cpp}
    CodeGen CodeGenerator;
    CodeGenerator.compile(Tree);
    return 0;
}
\end{cpp}

\end{enumerate}

现在，已经成功地为用户输入创建了一些IR代码。将目标代码生成委托给LLVM llc静态编译器，这样就完成了编译器的实现。我们将所有组件链接在一起以创建calc应用程序。

运行时库由一个文件rtcalc.c组成，实现了calc\_read()和calc\_write()函数，用C语言实现:

\begin{cpp}
#include <stdio.h>
#include <stdlib.h>

void calc_write(int v)
{
    printf("The result is: %d\n", v);
}
\end{cpp}

calc\_write()只将结果值写入终端:

\begin{cpp}
int calc_read(char *s)
{
    char buf[64];
    int val;
    printf("Enter a value for %s: ", s);
    fgets(buf, sizeof(buf), stdin);
    if (EOF == sscanf(buf, "%d", &val))
    {
        printf("Value %s is invalid\n", buf);
        exit(1);
    }
    return val;
}
\end{cpp}

calc\_read()从终端读取一个整数。不能阻止用户输入字母或其他字符，所以必须仔细检查输入。若输入不是数字，则退出应用程序。更复杂的方法是让用户意识到问题，并再次要求提供一个数字。

下一步是构建并试用我们的编译器calc，这是一个从表达式创建IR的应用程序。

\mySubsubsection{2.6.3.1}{构建和测试calc应用程序}

为了构建calc，首先需要在原始src目录之外创建一个新的CMakeLists.txt文件，其中包含所有源文件实现:

\begin{enumerate}
\item
首先，将最低所需的CMake版本设置为LLVM所需的值，并将项目名称命名为calc:

\begin{cmake}
cmake_minimum_required (VERSION 3.20.0)
project ("calc")
\end{cmake}

\item
接下来，需要加载LLVM包，将LLVM提供的CMake模块目录添加到搜索路径中:

\begin{cmake}
find_package(LLVM REQUIRED CONFIG)
message("Found LLVM ${LLVM_PACKAGE_VERSION}, build type ${LLVM_BUILD_TYPE}")
list(APPEND CMAKE_MODULE_PATH ${LLVM_DIR})
\end{cmake}

\item
还需要从LLVM中添加定义和包含路径，使用的LLVM组件通过函数调用映射到库名:

\begin{cmake}
separate_arguments(LLVM_DEFINITIONS_LIST NATIVE_COMMAND ${LLVM_DEFINITIONS})
add_definitions(${LLVM_DEFINITIONS_LIST})
include_directories(SYSTEM ${LLVM_INCLUDE_DIRS})
llvm_map_components_to_libnames(llvm_libs Core)
\end{cmake}

\item
最后，还需要在构建中包含src子目录，这是本章中所有C++的实现:

\begin{cmake}
add_subdirectory ("src")
\end{cmake}

\end{enumerate}

还需要在src子目录中添加一个新的CMakeLists.txt文件。src目录中的CMake描述如下所示，只需定义可执行文件的名称calc，然后列出要编译的源文件和要链接的库:

\begin{cmake}
add_executable (calc
    Calc.cpp CodeGen.cpp Lexer.cpp Parser.cpp Sema.cpp)
target_link_libraries(calc PRIVATE ${llvm_libs})
\end{cmake}

最后，可以开始构建calc应用程序。在src目录之外，创建一个新的构建目录并对其进行修改，就可以运行CMake配置和构建调用:

\begin{shell}
$ cmake -GNinja -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++
-DLLVM_DIR=<path to llvm installation configuration> ../
$ ninja
\end{shell}

我们现在有了一个新构建的、功能性的calc应用程序，可以生成LLVM IR代码。这可以进一步与llc(LLVM静态后端编译器)一起使用，将IR代码编译成目标文件。

然后，可以使用喜欢的C编译器来链接小型运行时库。在Unix-x86上，可以键入以下命令:

\begin{shell}
$ calc "with a: a*3" | llc –filetype=obj -relocation-model=pic –o=expr.o
$ clang –o expr expr.o rtcalc.c
$ expr
Enter a value for a: 4
The result is: 12
\end{shell}

在其他Unix平台(如AArch64或PowerPC)上，需要删除-relocationmodel=pic选项。

在Windows上，需要使用cl编译器:

\begin{shell}
$ calc "with a: a*3" | llc –filetype=obj –o=expr.obj
$ cl expr.obj rtcalc.c
$ expr
Enter a value for a: 4
The result is: 12
\end{shell}

现在，已经创建了第一个基于llvm的编译器!请花点时间练习不同的表达方式。特别要检查乘法运算符是否在加法运算符之前求值，以及使用括号是否改变了求值顺序(例如四则运算)。











